Sau khi được tha sớm khỏi nhà tù, Tyson dễ dàng giành chiến thắng trong trận đấu với Peter McNeeley và Buster Mathis Jr. Trận đấu trở lại đầu tiên của Tyson thu về hơn 96 triệu đô la Mỹ trên toàn thế giới, bao gồm một kỷ lục Hoa Kỳ 63 triệu đô la Mỹ cho truyền hình PPV. Có 1,52 triệu hộ gia đình đăng ký mua xem trực tiếp trận đấu, tạo ra kỷ lục về số người xem và doanh thu PPV.[83] Cuộc chiến kéo dài 89 giây đã gợi ra những lời chỉ trích rằng ban lãnh đạo của Tyson đã cho Tyson đấu với những võ sĩ kém cỏi để đảm bảo chiến thắng dễ dàng cho sự trở lại của anh.[84] TV Guide đã đưa trận đấu Tyson-McNeeley vào danh sách 50 khoảnh khắc thể thao truyền hình vĩ đại nhất mọi thời đại của họ trong năm 1998.[85]

Tyson đã lấy lại được một đai vô địch bằng cách dễ dàng giành được danh hiệu WBC trước Frank Bruno vào tháng 3 năm 1996. Đó là trận đấu thứ hai giữa hai người và Tyson đã hạ gục Bruno ở vòng thứ ba.[86] Năm 1996, Lennox Lewis đã từ chối khoản tiền 13,5 triệu đô la để đấu với Tyson. Đây sẽ là số tiền cho trận đấu cao nhất của Lewis cho đến nay. Sau đó, Lewis đã chấp nhận 4 triệu đô la từ Don King để bước sang một bên và cho phép Tyson chiến đấu với Bruce Seldon với số tiền dự kiến là 30 triệu đô la Mỹ thay vì với ý định rằng nếu Tyson đánh bại Seldon, Tyson sẽ chiến đấu với Lewis tiếp theo.[87] Tyson đã có thêm đai vô địch WBA bằng cách đánh bại nhà vô địch Seldon trong hiệp đầu tiên vào tháng 9 năm đó. Seldon bị chỉ trích nặng nề và bị chế giễu trên báo chí nổi tiếng vì dường như sụp đổ trước những cú đấm vô thưởng vô phạt của Tyson.[88]

Các trận đấu Tyson-Holyfield

Tyson vs Holyfield I

Tyson đã cố gắng bảo vệ danh hiệu WBA trước Evander HolyfieldAnh, người cũng đang trong cuộc chiến thứ tư trong lần trở lại với sàn đấu quyền. Holyfield đã nghỉ hưu vào năm 1994 sau khi mất chức vô địch của mình khi thua Michael Moorer. Người ta nói rằng Don King và những người khác đã cho rằng cựu vô địch Holyfield, lúc đó 34 tuổi và là một tay đấm được cho là kém hơn, là một võ sĩ đã hết thời.[89]

Vào ngày 9 tháng 11 năm 1996, tại Las Vegas, Nevada, Tyson phải đối mặt với Holyfield trong một trận đấu được mang tên "Finally (Cuối cùng)". Trong một diễn biến đáng ngạc nhiên, Holyfield, người được nhiều nhà bình luận cho rằng gần như không có cơ hội chiến thắng,[90] đã đánh bại Tyson bằng TKO khi trọng tài Mitch Halpern dừng trận đấu ở hiệp 11.[91] Holyfield trở thành võ sĩ thứ hai giành được đai vô địch hạng nặng ba lần. Chiến thắng của Holyfield đã bị những lời cáo buộc từ đội của Tyson rằng Holyfield đã dùng những cú húc đầu thường xuyên [92] trong trận đấu. Mặc dù các cú húc đầu này đã được trọng tài kết luận là do tình cờ,[92] chúng sẽ trở thành một điểm gây tranh cãi trong trận tái đấu sau đó.[93]

Tyson vs Holyfield II và sau đó

Tyson và Holyfield đã chiến đấu với nhau một lần nữa vào ngày 28 tháng 6 năm 1997. Ban đầu, Halpern được cử làm trọng tài, nhưng sau khi đội của Tyson phản đối, Halpern đã nhường bước để ủng hộ Mills Lane.[94] Trận tái đấu rất được mong đợi này được đặt tên là The Sound and the Fury, và nó được tổ chức tại MGM Grand Garden Arena, Las Vegas, nơi diễn ra trận đấu đầu tiên. Đó là một sự kiện sinh lợi nhuận, thu hút sự chú ý nhiều hơn so với lần đầu tiên và thu về 100 triệu đô la Mỹ. Tyson nhận được 30  triệu đô la và Holyfield nhận 35 triệu đô la, khoản tiền thưởng cho quyền Anh chuyên nghiệp được trả cao nhất cho đến năm 2007 [95][96] Có1.99 triệu hộ gia đình bỏ tiền xem trực tiếp trận đấu, lập kỷ lục tỷ lệ mua trả tiền theo lượt xem cho đến ngày 5 tháng 5 năm 2007, bị trận đấu Oscar De La Hoya vs. Floyd Mayweather Jr. vượt qua [96][97]

Sớm trở thành một trong những sự kiện gây tranh cãi nhất trong các môn thể thao hiện đại,[98] trận đấu đã dừng lại ở cuối hiệp thứ ba, với Tyson bị loại (disqualified)[99] vì cắn cả hai tai của Holyfield. Lần đầu tiên Tyson cắn Holyfield, trận đấu tạm thời dừng lại. Trọng tài Mills Lane đã trừ Tyson hai điểm và cuộc chiến lại tiếp tục. Tuy nhiên, sau khi trận đấu được tiếp tục, Tyson cắn tai Holyfield một lần nữa, dẫn đến việc anh ta bị loại (disqualified) và Holyfield đã thắng trận đấu. Một vết cắn nghiêm trọng tới mức đã cắt đứt một phần tai phải của Holyfield, được tìm thấy trên sàn đấu sau trận.[100] Tyson sau đó tuyên bố rằng hành động của anh ta là sự trả thù cho Holyfield liên tục húc đầu vào Tyson trong trận trước mà không hề bị phạt.[93] Hỗn loạn xảy ra sau khi kết thúc trận đấu và thông báo về quyết định này, một cuộc bạo loạn gần xảy ra trên sàn đấu và một số người bị thương.[101] Tyson Holyfield II là cuộc chiến danh hiệu hạng nặng đầu tiên trong hơn 50 năm kết thúc với một võ sĩ bị loại (disqualified).[102]

Như một hậu quả sau đó từ vụ việc, số tiền thưởng 30 triệu đô la của Tyson đã bị Ủy ban quyền anh bang Nevada trừ ngay 3 triệu đô la (số tiền lớn nhất có thể trừ từ tiền thưởng một cách hợp pháp vào thời điểm đó).[103] Hai ngày sau cuộc chiến, Tyson đã đưa ra một tuyên bố,[104] xin lỗi Holyfield vì hành động của mình và xin không bị cấm thi đấu suốt đời vì vụ việc này.[105] Tyson bị lên án mọi mặt trên các phương tiện truyền thông nhưng không phải không có người bảo vệ. Tiểu thuyết gia và nhà bình luận Kinda Dunn đã viết một chuyên mục chỉ trích khả năng thể thao của Holyfield trong trận đấu gây tranh cãi và buộc tội các phương tiện truyền thông đã thiên vị chống lại Tyson.[106]

Vào ngày 9 tháng 7 năm 1997, giấy phép thi đấu quyền Anh của Tyson đã bị Ủy ban thể thao bang Nevada hủy bỏ trong một cuộc bỏ phiếu hoàn toàn nhất trí; anh cũng bị phạt 3 triệu đô la Mỹ và phải trả các chi phí pháp lý của phiên điều trần.[107] Vì hầu hết các ủy ban thể thao của tiểu bang đều tôn trọng các lệnh trừng phạt do các tiểu bang khác áp đặt, điều này thực sự khiến Tyson không thể thi đấu quyền Anh ở Hoa Kỳ. Việc thu hồi giấy phép này không phải là vĩnh viễn, vì ủy ban đã bỏ phiếu với tỷ lệ 4-1 để khôi phục giấy phép đấu quyền Anh của Tyson vào ngày 18 tháng 10 năm 1998.[108]

Trong thời gian rời xa quyền Anh năm 1998, Tyson đã xuất hiện với tư cách khách mời tại WrestleMania XIV với tư cách là người đảm bảo trật tự cho trận đấu chính giữa Shawn Michaels và Steve Austin. Trong thời gian này, Tyson cũng là một thành viên không chính thức của sàn tập D-Generation X của Michaels. Tyson được trả 3 triệu đô la Mỹ cho việc làm khách mời đảm bảo trật tự cho trận đấu tại WrestleMania XIV.[109]